#if defined(__GNUC__) || defined(__clang__)
using i128 = __int128;
using u128 = unsigned __int128;
#else
#error "int128 is only supported on GCC and Clang compilers"
#endif

namespace std {
template <>
class numeric_limits<i128> {
public:
    static constexpr bool is_specialized = true;
    static constexpr i128 min() { return static_cast<u128>(1) << 127; }
    static constexpr i128 max() { return ~(static_cast<u128>(1) << 127); };
};
} // namespace std

std::ostream& operator<<(std::ostream& os, i128 n) {
    if (n == 0) return os << '0';
    
    const bool is_negative = n < 0;
    u128 abs_n = is_negative ? -static_cast<u128>(n) : static_cast<u128>(n);
    
    char buffer[40] = {0};
    char* ptr = buffer + sizeof(buffer) - 1;
    
    while (abs_n > 0) {
        *--ptr = '0' + abs_n % 10;
        abs_n /= 10;
    }
    
    if (is_negative) *--ptr = '-';
    return os << ptr;
}


std::istream& operator>>(std::istream& is, i128& n) {
    std::string s;
    is >> s;
    
    try {
        n = toi128(s);
    } catch (const std::exception& e) {
        is.setstate(std::ios::failbit);
        throw;
    }
    return is;
}

i128 toi128(const std::string& s) {
    if (s.empty()) throw std::invalid_argument("Empty input string");
    
    size_t pos = 0;
    const bool negative = (s[0] == '-');
    if (negative || s[0] == '+') pos++;
    if (pos >= s.size()) throw std::invalid_argument("Invalid number format");
    
    constexpr i128 max_prev = std::numeric_limits<i128>::max() / 10;
    constexpr i128 max_digit = std::numeric_limits<i128>::max() % 10;
    
    i128 result = 0;
    for (; pos < s.size(); ++pos) {
        if (!std::isdigit(s[pos])) {
            throw std::invalid_argument("Non-digit character in input");
        }
        
        const int digit = s[pos] - '0';
        if (result > max_prev || (result == max_prev && digit > max_digit + negative)) {
            throw std::overflow_error("i128 overflow");
        }
        
        result = result * 10 + digit;
    }
    return negative ? -result : result;
}

i128 sqrti128(i128 n) {
    if (n < 0) throw std::domain_error("Square root of negative number");
    if (n == 0) return 0;
    
    i128 low = 0;
    i128 high = (static_cast<u128>(1) << 63) - 1;
    
    while (low < high) {
        const i128 mid = (low + high + 1) / 2;
        
        bool overflow = false;
        i128 square;
        if (mid > std::numeric_limits<i128>::max() / mid) {
            overflow = true;
        } else {
            square = mid * mid;
        }
        
        if (overflow || square > n) {
            high = mid - 1;
        } else {
            low = mid;
        }
    }
    return low;
}

i128 gcd(i128 a, i128 b) noexcept {
    if (a == 0) return b;
    if (b == 0) return a;
    
    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        ++shift;
    }
    
    while (a != b) {
        while ((a & 1) == 0) a >>= 1;
        while ((b & 1) == 0) b >>= 1;
        if (a > b) std::swap(a, b);
        b -= a;
    }
    return a << shift;
}